package basic.courseLearn07.problem;

import basic.courseLearn07.Graph;
import basic.courseLearn07.Node;
import org.junit.Test;

import java.util.*;

//深度优先遍历
public class DepthFirstTraversal {

    private HashSet<Node> set ;

    public void init(){
        set = new HashSet<Node>();
    }



    public void traversal(Node root){
        //1. 访问root节点
        System.out.print(root.value + " ");
        set.add(root);

        //2. 对节点的nexts进行遍历
        for (Node next : root.nexts) {
            if (!set.contains(next)) {
                traversal(next);
            }
        }

    }

    @Test
    public void test(){
        Graph graph = new Graph();
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        node1.getNexts().add(node2);
        node1.getNexts().add(node4);
        node1.getNexts().add(node6);
        node2.getNexts().add(node1);
        node2.getNexts().add(node3);
        node3.getNexts().add(node2);
        node3.getNexts().add(node5);
        node3.getNexts().add(node6);
        node4.getNexts().add(node1);
        node5.getNexts().add(node3);
        node6.getNexts().add(node1);
        node6.getNexts().add(node3);
        HashMap<Integer, Node> map = new HashMap<>();
        map.put(1, node1);
        map.put(2, node2);
        map.put(3, node3);
        map.put(4, node4);
        map.put(5, node5);
        map.put(6, node6);
        graph.setNodes(map);
        init();
        traversal(node1);

    }



}
